| 翻訳と辞書 |
| Finger search ： ウィキペディア英語版 |
Finger search
In computer science, a finger search on a data structure is an extension of any search operation that structure supports, where a reference (finger) to an element in the data structure is given along with the query. While the search time for an element is most frequently expressed as a function of the number of elements in a data structure, finger search times are a function of the distance between the element and the finger.
In a set of ''n'' elements, the distance ''d''(''x'',''y'') (or simply ''d'' when unambiguous) between two elements ''x'' and ''y'' is their difference in rank. If ''x'' and ''y'' are the ''i''th and ''j''th largest elements in the structure, then the difference in rank is |''i'' - ''j''|. If a normal search in some structure would normally take O(f(''n'')) time, then a finger search for ''x'' with finger ''y'' should ideally take O(f(''d'')) time. Remark that since ''d'' ≤ ''n'', it follows that in the worst case, finger search is only as bad as normal search. However, in practice these degenerate finger searches do more work than normal searches. For instance, if f(''n'') is log(''n''), and finger search does twice as many comparisons as normal search in the worst case, it follows that finger search is slower when ''d'' > √''n''. Therefore, finger search should only be used when one can reasonably expect the target to actually be close to the finger.
==Implementations==
Some popular data structures support finger search with no additional changes to the actual structure. In structures where searching for an element ''x'' is accomplished by narrowing down an interval over which ''x'' can be found, finger search from ''y'' is typically accomplished by reversing the search process from ''y'' until the search interval is large enough to contain ''x'', at which point search proceeds as normal.
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「Finger search」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|